package Map;

class Node{
    public int key;
    Node left=null;
    Node right=null;
    public Node(int key){
        this.key=key;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
public class BinarySearchTree {
    private Node root=null;

    //把新的元素插入到树中
    public void insert(int key){
        //如果是空树，直接把root指向新的节点
        Node newNode=new Node(key);
        if (root == null){
            root=newNode;
            return;
        }
        // 普通的树, 需要找到要插入的位置, 再进行插入.
        // cur 用来找待插入元素的位置.
        // parent 记录 cur 的父元素.
        Node cur=root;
        Node parent=null;
        while (cur!= null){
            if (key<cur.key){
                parent=cur;
                cur=cur.left;
            }else if(key>cur.key){
                parent=cur;
                cur=cur.right;
            }else {
                // 对于相等的情况, 存在多种不同的处理方式.
                // 当前不允许重复 key 存在, 并且是 Set 只保存key, 直接 return.
                return;
            }
        }
        // 通过上述循环, 最终得到 cur 为 null 情况. 此时 parent 就是叶子节点, 也就是要新插入元素的父亲.
        // 就需要把 newNode 插入到 parent 的子节点上.
        // 新节点, 应该在 parent 的左子树, 还是右子树上呢??
        if (key<parent.key){
            parent.left=newNode;
        }else {
            parent.right = newNode;
        }
    }

    //查找key是否在树中存在，如果存在返回对应的节点位置;不存在返回null
    public Node find(int key){
        if (root==null){
            return null;
        }
        Node cur=root;
        while(cur!= null){
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                // 相等, 找到了.
                return cur;
            }
        }
        // 循环结束, 已经找到叶子节点了, 还没找到 key, 说明不存在.
        return null;
    }

    // 删除二叉搜索树中的 key . 不存在就不做任何事情.
    public void remove(int key){
        if (root==null){
            return;
        }
        Node cur=root;
        Node parent=null;
        while (cur!=null){
            if (key<cur.key){
                parent = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                // 往右找
                parent = cur;
                cur = cur.right;
            }else{
                removeNode(parent,cur);
                return;
            }
        }
    }
    private void removeNode(Node parent,Node cur){
        // 具体删除节点的时候, 要考虑四种情况
        // 1. cur 没有子树
        if (cur.left==null && cur.right==null){
            // 1.1 如果 cur 就是 root, 需要对 root 进行调整.
            if (cur== root){
                root = null;
                return;
            }
            // 1.2 cur 不是 root, 同时 cur 是 parent 的左子树.
            if (cur == parent.left){
                parent.left = null;
                return;
            }
            // 1.3 cur 不是 root, 同时 cur 是 parent 的右子树
            if (cur == parent.right) {
                // 把右子树置空, 就相当于删除了 cur
                parent.right = null;
                return;
            }
            return;
        }
        // 2. cur 只有左子树
        //    此处仔细思考发现, 1 和 2 是可以合并的. 整体的条件就直接写作 cur.right == null
        //    无论 cur.left 是否为 null 这一套代码都能满足.
        if (cur.left!=null && cur.right==null){
            // 2.1 cur 为 root
            if (cur== root){
                root=cur.left;
                return;
            }
            // 2.2 cur 不是 root, 同时 cur 是 parent 的左子树
            if (cur == parent.left) {
                parent.left = cur.left;
                return;
            }
            // 2.3 cur 不是 root, 同时 cur 是 parent 的右子树
            if (cur == parent.right) {
                parent.right = cur.left;
                return;
            }
            return;
        }
        // 3. cur 只有右子树
        if (cur.left == null && cur.right != null) {
            // 3.1 cur 为 root
            if (cur == root) {
                root = cur.right;
                return;
            }
            // 3.2 cur 不是 root, 是 parent 的左子树
            if (cur == parent.left) {
                parent.left = cur.right;
                return;
            }
            // 3.3 cur 不是 root, 是 parent 的右子树
            if (cur == parent.right) {
                parent.right = cur.right;
                return;
            }
        }
        // 4. cur 有两个子树
        // 这种情况下, 不需要考虑 cur 是不是 root 的情况. 并没有真正的删除 cur 指向的节点. 即使 cur 是 root, 也无需修改 root 的指向.
        // 因为实际删除的是 "替罪羊节点"
        // 4.1 首先需要找到右子树中的最小值 => 替罪羊.
        // 后续要删除替罪羊, 也顺便把替罪羊的父亲, 记录一下.
        Node goat=cur.right;
        Node goatParent=cur;
        while (goat.left!=null){
            goatParent=goat;
            goat=goat.left;
        }
        // 循环结束之后, goat 就是指向右子树的最左侧元素了.
        // 4.2 移花接木, 把替罪羊的值, 赋值到 cur 节点中.
        cur.key=goat.key;
        // 4.3 真正删除 goat 节点 (goat 是没有左子树的, 让 goatParent 直接连上 goat 的右子树即可)
        //     即使 goat 的右子树也是空, 不影响.
        //     这个代码还有个坑. goat 不一定就是 goatParent 的左子树!!(当右边没有左子树时)
        if (goat==goatParent.left){
            goatParent.left=goat.right;
        }else {
            goatParent.right=goat.right;
        }

    }



    public static void preOrder(Node node){
        if (node==null){
            return;
        }
        System.out.print(node.key+"");
        preOrder(node.left);
        preOrder(node.right);
    }
    public static void inOrder(Node node){
        if (node==null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.key+"");
        inOrder(node.right);
    }
    public void print(){
        System.out.println("线序遍历的结果:");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历的结果:");
        inOrder(root);
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 4, 0, 5, 9, 7, 8, 6, 10};
        // BinarySearchTree 也在很多资料上被缩写成 BST
        BinarySearchTree tree = new BinarySearchTree();
        for (int key:arr){
            tree.insert(key);
        }
        tree.print();
        System.out.println(tree.find(9));
    }
}
